#include<bits/stdc++.h>
using namespace std;
int vis[11];
int mp[11][11];
int n,e,bf[100];
void dfs(int f)
{
	for(int a=0;a<n;a++){
		if(mp[f][a]==1&&vis[a]==0){
			vis[a]=1;
			cout<<a<<' ';
			dfs(a);
		}
	}
	return;
}
int l=0,r=0;
void bfs(int x)
{
	while(r!=l)
	{
		for(int a=0;a<n;a++){
			if(mp[x][a]==1&&vis[a]==0){
					vis[a]=1;
					cout<<a<<' ';
					bf[r++]=a;
			}
		}
		x = bf[++l];
	}
	return ;
}
int main()
{	
	memset(mp,0,sizeof(mp));
	cin>>n>>e;
	while(e--)
	{
		int a,b;
		cin>>a>>b;
		mp[a][b]=mp[b][a]=1;
	}
	
	memset(vis,0,sizeof(vis));//dfs
	for(int i=0;i<n;i++){
		if(vis[i] == 0){
			vis[i]=1;
			cout<<"{ "<<i<<" ";
			dfs(i);
			cout<<"}"<<endl;
		}
	}
	memset(vis,0,sizeof(vis));//bfs
	for(int a=0;a<n;a++){
		if(vis[a]==0){
			vis[a]=1;
			l=0,r=1;
			bf[l]=a;
			cout<<"{ "<<a<<' ';
			bfs(bf[l]);
			cout<<'}'<<endl;
		}
	}
	
}

